package util;

import java.util.Arrays;

public class ArraySortDemo {
    public static void main(String[] args) {
        int[] arr = {6, 5, 2, 8, 2, 1, 3};

        //bubbleSort(arr);

        quicksort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    public static int[] bubbleSort(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i + 1] < arr[i]) {
                    arr[i + 1] = arr[i + 1] ^ arr[i];
                    arr[i] = arr[i + 1] ^ arr[i];
                    arr[i + 1] = arr[i + 1] ^ arr[i];

                }
            }
        }
        return arr;
    }

    public static int[] selectSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = i+1;j<arr.length;j++){
                if(arr[j]<arr[j-1]){
                arr[i] = arr[i]^arr[j];
                arr[j] = arr[i]^arr[j];
                arr[i] = arr[i]^arr[j];
            }
        }
    }
    return arr;
}
    public static void quicksort(int[] arr,int start,int end){
    if(start<end){
        int index = getIndex(arr,start,end);
        quicksort(arr,0,index-1);
        quicksort(arr,index+1,end);
    }}

    private static int getIndex(int[] arr,int start,int end){
        int i = start;
        int j = end;
        int x = arr[0];
        while(i<j){
            while(i<j && arr[j]>=x)
                j--;
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = x;
        return i;
    }
}